package com.coder.algorithm.offer_2;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * 滑动窗口的最大值
 *
 * @author yuhushuan
 * @date 2020/7/2 10:53
 */
public class _59_1_MaxInSlidingWindow {
    private static List<Integer> maxInWindows(int[] data, int size) {
        if (data == null || size <= 0 || size > data.length) {
            return null;
        }
        ArrayList<Integer> maxInWindow = new ArrayList<>();
        // 将最大值下标放first
        Deque<Integer> index = new ArrayDeque<>();

        for (int i = 0; i < size; i++) {
            while (!index.isEmpty() && data[i] >= data[index.peekLast()]) {
                index.pollLast();
            }
            index.offerLast(i);
        }

        for (int i = size; i < data.length; i++) {
            // 将窗口最大值存入
            maxInWindow.add(data[index.peekFirst()]);

            // 判断新值，如果大于最大值，则替换
            while (!index.isEmpty() && data[i] >= data[index.peekLast()]) {
                index.pollLast();
            }
            if (!index.isEmpty() && index.peekFirst() <= i - size) {
                index.pollFirst();
            }
            index.offerLast(i);
        }
        maxInWindow.add(data[index.peekFirst()]);
        return maxInWindow;
    }

    public static void main(String[] args) {
        // 功能测试
        // 无序数组
        print(new int[]{2, 3, 4, 2, 6, 2, 5, 1}, 3);
        // 单调递增
        print(new int[]{2, 3, 4, 5, 6, 7, 8, 9}, 3);
        // 单调递减
        print(new int[]{9, 8, 7, 6, 5, 4, 3, 2}, 3);

        // 边界值
        // 滑动窗口为 0、1、数组长度、大于数组长度
        print(new int[]{2, 3, 4, 2, 6, 2, 5, 1}, 0);
        print(new int[]{2, 3, 4, 2, 6, 2, 5, 1}, 1);
        print(new int[]{2, 3, 4, 2, 6, 2, 5, 1}, 8);
        print(new int[]{2, 3, 4, 2, 6, 2, 5, 1}, 9);

        // 特殊输入测试
        print(null, 1);
    }

    private static void print(int[] data, int size) {
        System.out.println("数组为：\n" + Arrays.toString(data));
        System.out.println("滑动窗口大小为：" + size);
        System.out.println("滑动窗口的最大值为：\n" + maxInWindows(data, size));
        System.out.println();
    }
}
